package demo11;

import java.util.*;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Day3 {


    public int totalFruit(int[] fruits) {
        int[] hash = new int[100000];
        int left = 0;
        int right = 0;
        int max = 0;
        int count = 0;
        int len = fruits.length;
        while(right < len) {
            hash[fruits[right]]++;
            if(hash[fruits[right]] == 1) {
                count++;
            }
            while(count > 2) {
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0) {
                    count--;
                }
                left++;
            }
            if(count <= 2) {
                int n = right - left + 1;
                max = Math.max(n,max);
            }
            right++;
        }
        return max;

    }
    public int minOperations(int[] nums, int x) {
        int sum = 0;
        for(int a : nums) {
            sum += a;
        }
        int tar = sum - x;
        if(tar < 0) {
            return -1;
        }
        int left = 0;
        int right = 0;
        int len = nums.length;
        int all = 0;
        int max = 0;
        while(right < len) {
            all += nums[right];
            while(all > tar) {
                all -= nums[left];
                left++;
            }
            if(all == tar) {
                int n = right - left + 1;
                max = Math.max(max,n);
            }
            right++;
        }
        return max == 0 ? -1 : (len - max);
    }



    public int longestOnes(int[] nums, int k) {
        int max = 0;
        int left = 0;
        int right = 0;
        int zero = 0;
        while(right < nums.length) {
            while(right < nums.length && (nums[right] == 1 || zero < k)) {
                if(nums[right] == 0) {
                    zero++;
                }
                max = Math.max(max,(right - left + 1));
                right++;
            }
            while(zero > k) {
                if(nums[left] == 0) {
                    zero--;
                }
                left++;
            }
        }
        return max;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new LinkedList<>();
        int a = 0;
        while (a < nums.length) {
            int b = a + 1;
            int c = nums.length - 1;
            while (b < c) {
                if (nums[b] + nums[c] + nums[a] > 0) {
                    c--;
                } else if (nums[b] + nums[c] + nums[a] < 0) {
                    b++;
                } else {
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[a]);
                    list.add(nums[b]);
                    list.add(nums[c]);
                    lists.add(list);
                    b++;
                    c--;

                }
                while (b < c && nums[b] == nums[b - 1]) {
                    b++;
                }
                while (c + 1 < nums.length && b < c && nums[c] == nums[c + 1]) {
                    c--;
                }

            }
            while (a + 1 < nums.length && nums[a] == nums[a + 1]) {
                a++;
            }
            a++;
        }
        return lists;
    }

    public boolean chkPalindrome(ListNode A) {
        //1.找到中间节点
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.开始回文
        //ListNode cur = slow.next;
        //while(cur != null) {
        //  ListNode curNext = cur.next;
        //cur.next = slow;
        //slow = cur;
        //cur = curNext;
        //}

        while(slow.next != null) {
            ListNode cur = slow.next;
            cur.next = slow;
            slow = cur;
        }
        fast = A;
        //3.判断是否为回文结构
        while(fast != slow && fast.next != slow) {
            if(fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;


    }

    public ListNode partition(ListNode pHead, int x) {
        if(pHead == null) {
            return pHead;
        }
        //定义两个区间 as-ae  bs-be
        //小于x的区间
        ListNode as = pHead;
        ListNode ae = as;
        //大于等于x的区间
        ListNode bs = pHead;
        ListNode be = bs;
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                ae.next = cur;
                ae = cur;
            }else {
                be.next = cur;
                be = cur;
            }
            cur = cur.next;
        }
        ae.next = bs.next;
        be.next = null;
        return as.next;
    }

    public int calculateMinimumHP(int[][] dungeon) {

        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];

        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (i + 1 < m || j + 1 < n) {
                    if (i + 1 < m && j + 1 < n) {
                        int min = Math.min(dp[i][j+1],dp[i+1][j]);
                        if(dungeon[i][j] - min >= 0) {
                            dp[i][j] = 1;
                        }else {
                            dp[i][j] = min - dungeon[i][j];
                        }
                    } else if (i + 1 < m) {
                        if(dungeon[i][j] - dp[i][j+1] >= 0) {
                            dp[i][j] = 1;
                        }else {
                            dp[i][j] = dp[i][j + 1] - dungeon[i][j];
                        }
                    } else if (j + 1 < n) {
                        if(dungeon[i][j] - dp[i+1][j] >= 0) {
                            dp[i][j] = 1;
                        }else {
                            dp[i][j] = dp[i+1][j] - dungeon[i][j];
                        }
                    }
                }else{
                    dp[i][j] = dungeon[i][j] >= 0 ? 1 : 1-dungeon[i][j];
                }

            }
        }
        return dp[0][0];

    }


    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    public String largestNumber(int[] nums) {

        if (nums.length == 1) {
            return String.valueOf(nums[0]);
        }
        StringBuilder str = new StringBuilder();
        for(int i = 0; i < nums.length; i++) {
            int flag = 0;
            for(int j = 0; j < nums.length - i - 1; j++) {
                StringBuilder str1 = new StringBuilder();
                StringBuilder str2 = new StringBuilder();
                str1.append(nums[j]);
                str1.append(nums[j+1]);
                str2.append(nums[j+1]);
                str2.append(j);
                if (str2.compareTo(str1) > 0) {
                    swap(nums,j,j+1);
                    flag = 1;
                }
            }
            if(flag == 0) {
                break;
            }
        }
        for(int x : nums) {
            str.append(x);
        }
        if((str.toString()).charAt(0) == '0') {
            return "0";
        }
        return str.toString();
    }

    public int halveArray(int[] nums) {
        PriorityQueue<Double> queue = new PriorityQueue<>(new Comparator<Double>() {
            public int compare(Double o1, Double o2) {
                return o2.compareTo(o1);
            }
        });
        int count = 0;
        double sum = 0.0;
        for (int x : nums) {
            sum += (double) x;
            queue.offer((double) x);
        }
        double flag = sum;
        while (!queue.isEmpty()) {
            double top = queue.poll();
            flag -= top / 2;
            count++;
            queue.offer(top / 2);
            if (flag <= (sum / 2.0)) {
                return count;
            }
        }
        return -1;
    }

    public int getSum(int a, int b) {
        while(b != 0) {
            int m = a ^ b;
            int n = (a & b) << 1;
            a = m;
            b = n;
        }
        return a;
    }
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = 0;
        while(right < nums.length) {
            if(sum < target) {
                sum += nums[right];
                right++;
            }else if(sum > target) {
                sum -= nums[left];
                left++;
            }else {
                min = right - left + 1;
                sum -= nums[left];
                left++;
                right++;
            }
        }
        return min;
    }

    public int lengthOfLongestSubstring(String s) {
        int count = 0;
        int left = 0;
        int right = 0;
        int max = 0;
        HashSet<Character> set = new HashSet<>();
        while(right < s.length()) {
            if(!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                count++;
            }else {
                while(set.contains(s.charAt(left)) && s.charAt(left) != s.charAt(right)) {
                    set.remove(s.charAt(left));
                    left++;
                    count--;
                }
                left++;
                count--;
            }
            count = Math.max(count,right - left + 1);
            right++;
        }
        return count;
    }

    public int findMaxLength(int[] nums) {
        for(int x = 0; x < nums.length; x++) {
            if(nums[x] == 0) {
                nums[x] = -1;
            }
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        int ret = 0;
        int sum = 0;
        map.put(0,-1);
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int j = map.getOrDefault(sum,0);
            ret = Math.max(ret,i - j);
            map.put(sum, sum == 0 ? -1 : i);
        }
        return ret;
    }
}
